package stack

import (
	"gitee.com/hlwqds/go-algorithm/linkList"
)

type LinkedStack struct {
	head *linkList.LNode
	size int
}

func NewLinkedStack() *LinkedStack{
	return &LinkedStack{
		head: linkList.NewListHeader(),
		size: 0,
	}
}

func (s *LinkedStack) IsEmpty() bool {
	if s != nil && s.size != 0 {
		return false
	}
	return true
}

func (s *LinkedStack) Top() int {
	if s.IsEmpty() == true {
		panic("stack is empty")
	}
	return s.head.Next.Data
}

func (s *LinkedStack) Size() int {
	if s != nil {
		return s.size
	}
	return 0
}

func (s *LinkedStack) Push(d int) {
	if s == nil || s.head == nil {
		panic("the linkedStack pointer invalid")
	}
	tmp := &linkList.LNode{
		Data: d,
		Next: s.head.Next,
	}
	s.head.Next = tmp
	s.size++
}

func (s *LinkedStack) Pop() int {
	if s.IsEmpty() == true {
		panic("is Empty")
	}
	tmp := s.head.Next
	s.head.Next = tmp.Next
	s.size--
	return tmp.Data
}

func (s *LinkedStack) MoveBottomToTop() {
	if s.IsEmpty() {
		return
	}
	top := s.Pop()
	if s.IsEmpty() {
		s.Push(top)
	} else {
		s.MoveBottomToTop()
		top1 := s.Pop()
		s.Push(top)
		s.Push(top1)
	}
}

func (s *LinkedStack)ReverseStack(){
	if s.IsEmpty() {
		return
	}
	s.MoveBottomToTop()
	top := s.Pop()
	s.ReverseStack()
	s.Push(top)
}

func (s *LinkedStack) MoveBottomToTopSort(){
	if s.IsEmpty() {
		return
	}
	top := s.Pop()
	if !s.IsEmpty() {
		s.MoveBottomToTopSort()
		top1 := s.Top()
		//栈顶元素应该是最小的元素
		if top > top1 {
			s.Pop()
			s.Push(top)
			s.Push(top1)
			return
		}
	}
	s.Push(top)
}

func (s *LinkedStack) SortStack(){
	if s.IsEmpty() {
		return
	}
	//先将最大或者最小的数移至栈顶
	s.MoveBottomToTopSort()
	//将子栈排序后，将最大或者最小的数推入栈顶
	top := s.Pop()
	s.SortStack()
	s.Push(top)
}